# 二叉树的所有路径： https://leetcode-cn.com/problems/binary-tree-paths/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 和前面的题“路径总和II”，没啥大区别，唯一注意的是 path变成字符串是 不可变对象
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        """
            注意，不需要考虑 path的回溯问题， 也不需要 进行复制添加到 rst中， 字符串是不可类型
            另外注意回溯的方式，不改变当前函数中的 path 值， 传递到下层调用函数，是新的 局部变量 path
        """
        rst = []
        def dfs(node, path: list):
            # 1. 递归终止条件
            if not node: return False
            # 2. path 加上当前节点值
            path += str(node.val)
            # 3. 如果是叶子结点, path 添加到 rst中
            if not node.left and not node.right: 
                rst.append(path)

            # 4. 遍历左右节点
            dfs(node.left, path + "->")
            dfs(node.right, path + "->") 

        dfs(root, '')
        return rst